Decomposing Solution Sets of Polynomial Systems: A New Parallel Monodromy Breakup Algorithm

摘要

We consider the numerical irreducible decomposition of a positive dimensionalsolution set of a polynomial system into irreducible factors. Path trackingtechniques computing loops around singularities connect points on the sameirreducible components. The computation of a linear trace for each factorcertifies the decomposition. This factorization method exhibits a goodpractical performance on solution sets of relative high degrees. Using the same concepts of monodromy and linear trace, we present a newmonodromy breakup algorithm. It shows a better performance than the old methodwhich requires construction of permutations of witness points in order to breakup the solution set. In contrast, the new algorithm assumes a finer approachallowing us to avoid tracking unnecessary homotopy paths. As we designed the serial algorithm keeping in mind distributed computing, anadditional advantage is that its parallel version can be easily built.Synchronization issues resulted in a performance loss of the straightforwardparallel version of the old algorithm. Our parallel implementation of the newapproach bypasses these issues, therefore, exhibiting a better performance,especially on solution sets of larger degree.